package 校招笔试.美团笔试.美318;

import java.util.*;

public class Main {


    /*
     第一题：
     纯暴力 : 36%
     */
    public static void mainI(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int nums[][] = new int[10001][10001];
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            nums[x][y] = 1;
        }
        int ans = 0;
        for (int i = 0; i < 10001; i++) {
            for (int j = 0; j < 10001; j++) {
                if (nums[i][j] == 0) {
                    continue;
                }
                int count = 1;
                for (int x = 0; x < a && i + x < 10001; x++) {
                    for (int y = 0; y < b && y + j < 10001; y++) {
                        if (nums[i + x][j + y] == 1) {
                            count++;
                        }
                    }
                }
                ans = Math.max(ans, count);
            }
        }
        System.out.println(ans);
    }

    /*
     动动脑子,
     现根据  横坐标 x 排序, 找到满足 的横坐标的  这些点 收集起来 ,然后再 把这些 点(坐标) 按照  y 进行排序
     找到 满足 纵坐标的 这些点, 既满足 横坐标, 又满足 纵坐标的 这些点,收集起来取个最大值!
     */
    public static void mai2(String[] args) {
        int solution = new Main().solution();
        System.out.println(solution);
    }

    public int solution() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt(), ans = 0;
        int point[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            point[i][0] = sc.nextInt();
            point[i][1] = sc.nextInt();
        }
        Arrays.sort(point, (x, y) -> x[0] - y[0]);
        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>(); // collect  y
            for (int j = i; j < n; j++) {
                if (point[j][0] - point[i][0] > a) {
                    break;
                }
                list.add(point[j][1]);
            }
            // 对y 进行排序, 找到 y 也符合的点
            Collections.sort(list);
            for (int j = 0; j < list.size(); j++) {
                int count = 0;
                int minY = list.get(j);
                /*
                 这个过程其实可以二分的!
                 */
                for (int k = j; k < list.size(); k++) {
                    if (list.get(k) - minY > b) {
                        break;
                    }
                    count++;
                }
                ans = Math.max(ans, count);
            }
        }
        return ans;
    }

    /*
     第二题： 彩带问题
     */
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(new Main().solution(nums, k));
    }

    public int solution(int nums[], int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        int l = 0, r = 0;
        while (r < nums.length) {
            map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);
            while (map.size() > k) {
                int num = map.get(nums[l]);
                if (num - 1 == 0) {
                    map.remove(nums[l]);
                } else {
                    map.put(nums[l], num - 1);
                }
                l++;
            }
            ans = Math.max(ans, r - l + 1);
            r++;
        }

        return ans;
    }


    /*
     不是动态规划写不出来
     而是这条路径，不知道该怎么去找，真他妈离谱;
     这个题, 本身并不难, 只是 你并不知道,在 求出最优解的情况下, 对 产生最优解路径的一个回溯 追踪 ( 没写过主要是) 而这个题, 就是这样
     */
    public static void mainIIII(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int money = sc.nextInt();
        int y = sc.nextInt();
        int nums[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = sc.nextInt();
            nums[i][1] = sc.nextInt();
        }
        int[] recursion = new Main().recursion(0, 0, y, money, nums);
        System.out.println(recursion[0] + " " + recursion[1]);
    }

    public int[] recursion(int index, int cost, int count, int money, int nums[][]) {
        if (index == nums.length || cost > money || count == 0) {
            return new int[]{0, 0};
        }
        int ans1[], ans2[], ans3[];
        // no
        ans1 = recursion(index + 1, cost, count, money, nums);
        ans2 = recursion(index + 1, cost - nums[index][0], count, money, nums);
        ans3 = recursion(index + 1, cost - nums[index][1], count - 1, money, nums);
        int sort[][] = new int[][]{ans1, ans2, ans3};
        Arrays.sort(sort, (a, b) -> a[0] - b[0]);
        int pay, cnt;
        if (sort[2] == ans1) {
            pay = 0;
            cnt = 0;
        } else if (sort[2] == ans2) {
            pay = nums[index][0];
            cnt = 1;
        } else {
            pay = nums[index][1];
            cnt = 1;
        }
        return new int[]{sort[2][0] + cnt, sort[2][1] + pay};
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int money = sc.nextInt();
        int y = sc.nextInt();
        int nums[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = sc.nextInt();
            nums[i][1] = sc.nextInt();
        }
        Integer dp[][][] = new Integer[n + 1][money + 1][y + 1];
        int ans = new Main().recursion(0,0,y,money,dp,nums);
        System.out.println(ans);
        // 遍历 dp 表, 找到 取得最优解时候 的 花费的 money
        int realCost = money;
        for(int rest = 0;rest <= money;rest++){
            for(int index = 0;index <= n ;index++ ){
//                System.out.println(Arrays.toString(dp[i][j]));
                for(int count = 0;count <= y;count++){
                    if(dp[index][rest][count] != null && dp[index][rest][count] == ans){
                        realCost = Math.min(realCost,rest);
                    }
                }
            }
        }
        System.out.println(ans + " " + realCost);

    }

    /*
           这种思路 好像 还可以 更好的理解, 还是java 版本的 (还是 路径记录)
          https://www.nowcoder.com/discuss/467067509045227520?sourceSSR=search

          这是学长的 写法: (感觉很简洁) (应该是进行了空间优化!)
          https://www.nowcoder.com/discuss/466884442846412800?sourceSSR=users

     */

    public int recursion(int index, int cost, int count, int money,Integer dp[][][], int nums[][]) {
        if (cost == money || index == nums.length) {
            return 0;
        }
        if (dp[index][cost][count] != null) {
            return dp[index][cost][count];
        }
        int ans1, ans2 = 0, ans3 = 0;
        // no choose
        ans1 = recursion(index + 1, cost, count,money, dp, nums);
        // 原价 前提是 能买
        if (cost + nums[index][0] <= money) {
            ans2 = recursion(index + 1, cost + nums[index][0],count,money, dp, nums) + 1;
        }
        // 半价
        if(cost + nums[index][1] <= money && count >= 1){
            ans3 = recursion(index + 1,cost + nums[index][1],count - 1,money,dp,nums) + 1;
        }
        return dp[index][cost][count] = Math.max(ans1,Math.max(ans2,ans3));
    }

    /*
     行不通?
     */
    public int recursion(int index, int rest, int count, Integer dp[][][], int nums[][]) {
        if (rest == 0 || index == nums.length) {
            return 0;
        }
        if (dp[index][rest][count] != null) {
            return dp[index][rest][count];
        }
        int ans1, ans2 = 0, ans3 = 0;
        // no choose
        ans1 = recursion(index + 1, rest, count, dp, nums);
        // 原价 前提是 能买
        if (rest - nums[index][0] >= 0) {
            ans2 = recursion(index + 1, rest - nums[index][0], count, dp, nums) + 1;
        }
        // 半价
        if(rest - nums[index][1] >= 0 && count >= 1){
            ans3 = recursion(index + 1,rest - nums[index][1],count - 1,dp,nums) + 1;
        }
        return dp[index][rest][count] = Math.max(ans1,Math.max(ans2,ans3));
    }



}
